package com.gxc.tree;

import java.util.Stack;

/**
 * 搜索二叉树  当前节点的左子节点比当前节点小，当前节点的右子节点比当前节点大
 */
public class SearchBinaryTrees {

    public static  int PRE_VALUE = Integer.MIN_VALUE;

    public static void main(String[] args) {
        TreeBean tree = Preorder.createSearchBinaryTrees();
        TreeBean tree2 = Preorder.createTree();

        //递归判断是否搜索二叉树
        System.out.println(recursion(tree));
        System.out.println(recursion(tree2));

        System.out.println("----------");
        Stack<TreeBean> stack = new Stack<>();
        //非递归断是否搜索二叉树
        System.out.println(nonRecursion(tree, stack));
        System.out.println(nonRecursion(tree2, stack));
    }

    /**
     * 非递归断是否搜索二叉树
     * @param treeBean
     * @return
     */
    private static boolean nonRecursion(TreeBean treeBean, Stack<TreeBean> stack) {
        int preValue = Integer.MIN_VALUE;
        while (treeBean!=null || !stack.empty()) {
            if (treeBean!=null) {
                stack.push(treeBean);
                treeBean = treeBean.left;
            } else {
                treeBean = stack.pop();
                if (treeBean.value<preValue) return false;
                else preValue = treeBean.value;
                treeBean = treeBean.right;
            }
        }
        return true;
    }

    /**
     * 递归判断是否搜索二叉树
     * @param head
     * @return
     */
    private static boolean recursion(TreeBean head) {
        if (head == null) return true;
        boolean isLeftBST = recursion(head.left);
        if (!isLeftBST) {
            return false;
        }
        if (head.value<PRE_VALUE) {
            return false;
        } else {
            PRE_VALUE = head.value;
        }
        return recursion(head.right);
    }
}
